/**
 * Clustering:cluster keywords by rock
 * input file:
 *   linksMatrixPath: keyword,weight,[(keyword_i,neighbors_num_i)(keyword_j,neighbors_num_j)...]\n
 * output file:
 *   clusterResultPath:cluser_id:keyword1,keyword2,....\n
 */
package cluster;
import java.io.*;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Collections;
import common.Config;
import common.Word;

public class Clustering{
    private LinkedList<Cluster> clusters = new LinkedList<Cluster>();

    /**
     * get cluster containing w.keyword,if not exsit,add a new cluster with w
     */
    private Cluster requestCluster( Word w ){
        for( ListIterator<Cluster> it=clusters.listIterator();it.hasNext(); ){
            Cluster cl = it.next();
            if( cl.containWord( w ) ){
                return cl;
            }
        }
        // not find,new one
        Cluster cl = new Cluster();
        clusters.add( cl );
        cl.addPoint( w );
        return cl;
    }
    
    /**
     * 将型如[(keyword,common_neighbors_num),...]的字符串转换成LinkedList<ClusterLink>
     */
    private LinkedList<ClusterLink> strToList( String str ){
        assert( str.startsWith("\\[") && str.endsWith("\\]"));
        LinkedList<ClusterLink> cl = new LinkedList<ClusterLink>();

        // remove "[(" and ")]"
        String substr = str.substring( 2, str.length()-2 );
        String[] links = substr.split("\\), \\(");
        //extract links list
        try{
            for( int i=0;i<links.length;i++ ){
                String[] pairs = links[i].split(",");
                
                Cluster another = requestCluster( new Word(pairs[0],0) );
                int num = Integer.parseInt( pairs[1] );
                //float goodness = computeGood( cl.size(),another.size(),num );
                ClusterLink clink = new ClusterLink( another,num,0 );
                cl.add( clink );
            			}
        }catch( NumberFormatException e ){
            System.err.println( "Wrong record:"+str +" "+e.toString());
        		}
        	return cl;
    }

    /**
     * sort clusters by max goodness in links,equal to build global heap in rock.
     */
    private void sortClusters(){
        Collections.sort( clusters );	// default sort by ascending order
        Collections.reverse( clusters );
    }

	protected void readData() throws IOException{
		String path = Config.linksMatrixPath;
		try{
			FileReader fr = new FileReader( path );
			BufferedReader br = new BufferedReader( fr );
            String line = br.readLine();
            while( line != null ){
                String[] items = line.trim().split( ",",3 );

                Word w = new Word( items[0],Float.parseFloat(items[1]) );
                Cluster cl = requestCluster( w );
                
				String str = items[ items.length -1 ].trim();
				cl.links = strToList( str );
                // compute goodness for links and sort them
                cl.sortLinks();

				line = br.readLine();
            }
			br.close();
			fr.close();
		}catch( FileNotFoundException e ){
			System.err.println( path + " not found!" );
			System.exit(1);
		}

        sortClusters();
	}

    private float maxGoodness(){
        Cluster cl = clusters.peekFirst();
        float maxg = cl==null?0:cl.maxGoodness();
        //debug
        System.out.println( "maxgoodness is "+maxg );
        //end
        return maxg;
    }

    /**
     * 更新所有包含cl和another的link:将another的num加到cl中，删除another,
     * 再调整cl再link list中的位置
     */
    private void updateLinks( Cluster cl,Cluster another ){
        for( ListIterator<Cluster> it=clusters.listIterator();it.hasNext(); ){
            Cluster cur = it.next();
            if( cur!=cl && cur!=another ){
          	  cur.updateLinkList( cl,another );
            		}
        }
        cl.ifRemoveLink( another );     
    }

    /**
     * 从全局clusters列表中移除指定簇
     * @para rcl is the cluster to be removed 
     */
    private void removeCluster( Cluster rcl ){
        for( ListIterator<Cluster> it=clusters.listIterator();it.hasNext(); ){
            if(  it.next() == rcl ){
                it.remove();
                return;
            }
        }
    }

    /**
     * 将簇another合并到簇cl，同时更新簇矩阵及相关的link(to improve,add cl to another)
     */
    private void merge( Cluster cl,Cluster another ){;
        // 1.merge points
        cl.merge( another );
        // 2.update relate cluster's links
        updateLinks( cl,another );
        // 3.remove cluster another
        removeCluster( another );
        // 4.对全局goodness列表重排序
        sortClusters();
    }

    protected void rock(){
        int k = Config.numClusters;
        float minGoodness = Config.minGoodness;

        while( clusters.size() > k && maxGoodness() > minGoodness ){
            Cluster cl = clusters.getFirst();
            Cluster another = cl.closest();
            merge( cl,another );
            //debug
            System.out.println("cluster remaining after merge:"+clusters.size() );
            //end
        		}
         //debug
         System.out.println("cluster size left:"+clusters.size());
         //end
    }

    protected void writeResult() throws IOException{
        FileWriter fw = new FileWriter( Config.clusterResultPath );
        int minPoints = Config.minPoints;
        for( ListIterator<Cluster> it=clusters.listIterator();it.hasNext(); ){
            Cluster cl = it.next();
            if( cl.numPoints() >= minPoints ){
          	  fw.write( cl.toString()+"\n");
            		}
        }
        fw.close();
    }

    public void run() throws IOException{
        readData();
        System.out.println("readData finished!Cluster num:"+clusters.size() );
        rock();
        System.out.println("Rock finished!");
        writeResult();
        System.out.println("writeResult finished:"+Config.clusterResultPath);
    }

    public static void main( String[] args ) throws IOException{
        Clustering rock = new Clustering();
		rock.run();		
		System.out.println("4.Clustering Completed!");
    }
}